1. Field of the Invention
The present invention relates to routing packets through a network based on header information in a payload of a packet received at a network device; and, in particular, to increasing efficiency by classifying the packet using hardware and aligning the header information with respect to a boundary of a cache line exchanged between memory and a processor in the network device.
2. Description of the Related Art
Networks of general purpose computer systems connected by external communication links are well known. The networks often include one or more network devices that facilitate the passage of information between the computer systems. A network node is a network device or computer system connected by the communication links.
Information is exchanged between network nodes according to one or more of many well known, new or still developing protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other based on information sent over the communication links. The protocols are effective at different layers of operation within each node, from generating and receiving physical signals of various types, to selecting a link for transferring those signals, to the format of information indicated by those signals, to identifying which software application executing on a computer system sends or receives the information. The conceptually different layers of protocols for exchanging information over a network are described in the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
Communications between nodes are typically effected by exchanging discrete packets of data. Each packet typically comprises 1] header information associated with a particular protocol, and 2] payload information that follows the header information and contains information to be processed independently of that particular protocol. In some protocols, the packet includes 3] trailer information following the payload and indicating the end of the payload information. The header includes information such as the source of the packet, its destination, the length of the payload, and other properties used by the protocol. Often, the data in the payload for the particular protocol includes a header and payload for a different protocol associated with a different, higher layer of the OSI Reference Model. The header for a particular protocol typically indicates a type for the next protocol contained in its payload. The higher layer protocol is said to be encapsulated in the lower layer protocol. The headers included in a packet traversing multiple heterogeneous networks, such as the Internet, typically include a physical (layer 1) header, a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header, as defined by the Open Systems Interconnection (OSI) Reference Model.
Some protocols span the layers of the OSI Reference Model. For example, the Ethernet local area network (LAN) protocol includes both layer 1 and layer 2 information. The International Electrical and Electronics Engineers (IEEE) 802.3 protocol, an implementation of the Ethernet protocol, includes layer 1 information and some layer 2 information. New protocols are developed to meet perceived needs of the networking community, such as a sub-network access protocol (SNAP), a virtual local area network (VLAN) protocol and a nested VLAN (QINQ) protocol. SNAP allows for the transmission of IP datagrams over Ethernet LANs. SNAP is a media independent header specified as an IEEE standard 802.2, which can be found at the world wide web domain ieee.org, the entire contents of which are hereby incorporated by reference as if fully set forth herein. The VLAN protocol is used by a group of devices on one or more LANs that are configured so that they can communicate as if they were attached to the same wire, when in fact they are located on a number of different LAN segments. The VLAN tagging is described at the time of this writing in IEEE standard 802.3ac available from the world wide web domain named ieee.org, the entire contents of which are hereby incorporated by reference as if fully set forth herein. The QINQ protocol is described at the time of this writing in the IEEE 802.1 ad standard found at ieee.org the entire contents of which are hereby incorporated by reference as if fully set forth herein. Some protocols follow a layer 2 protocol and precede a layer 3 protocol; and are said to be layer 2.5 protocols. For example, the multi-protocol layer switch (MPLS) is a layer 2.5 protocol. The MPLS protocol provides for the designation, routing, forwarding and switching of traffic flows through the network. MPLS is described at the time of this writing in Internet Engineering Task Force (IETF) request for comments (RFC) 3031 and RFC 3032 which can be found at the world wide web domain www.ietf.org in files named rfc3031.txt and rfc3031.tx in the file directory named rfc, the entire contents of which are hereby incorporated by reference as if fully set forth herein. In the following, an IEEE 802 protocol that does not involve such extensions as SNAP, VLAN, or QINQ is called an ARPA EN protocol, after the original Ethernet implementation developed by the Advance Research Projects Agency (ARPA).
Routers and switches are network devices that determine which communication link or links to employ to support the progress of packets through the network. Routers and switches can employ software executed by a general purpose processor, called a central processing unit (CPU), or can employ special purpose hardware, or can employ some combination to make these determinations and forward the packets from one communication link to another. Switches typically rely on special purpose hardware to quickly forward packets based on one or more specific protocols. For example, Ethernet switches for forwarding packets according to Ethernet protocol are implemented primarily with special purpose hardware.
While the use of hardware processes packets extremely quickly, there are drawbacks in flexibility. As protocols evolve through subsequent versions and as new protocols emerge, the network devices that rely on hardware become obsolete and have to ignore the new protocols or else be replaced. As a consequence, many network devices, such as routers, which forward packets across heterogeneous data link networks, include a CPU that operates according to an instruction set (software) that can be modified as protocols change.
Software executed operations in a CPU proceed more slowly than hardware executed operations, so there is a tradeoff between flexibility and speed in the design and implementation of network devices.
Some current routers implement sophisticated algorithms that provide high performance forwarding of packets based on combining layer 2 and layer 2.5 or layer 3 header information, or some other combination. For example, instead of making forwarding decisions separately on each packet in a stream of related packets directed from the same source node to the same destination node, these routers identify the packet stream from a unique signature derived from the layer 2 and layer 3 header information and forward each member of the stream according to the same decision made for the first packet in the stream. Because layer 2 headers are of variable length, depending on the protocol, the layer 3 header information may occupy different positions in the payloads of different packets. Because the layer 2 protocols may evolve in time, the processing of information from the layer 2 payload can advantageously be done using software and a CPU in the router.
For example, the Cisco Express Forwarding (CEF) software employed in routers, such as the Cisco 2600 Multiservice Platform router, recently available from Cisco Systems Incorporated of San Jose, Calif., determines the position of the layer 3 header information in a layer 2 payload and examines the layer 3 header information in memory. It has been estimated that the execution of software to find and examine the layer 3 header information in every packet received by the router involves about 10% of the CPU processing consumed by the router for packets with only the basic set of features enabled.
Additionally, it has been estimated that the software penalty for examining the packet header which is not aligned is 10% of the CEF processing. Processing of the misaligned packet header not only causes additional cache lines to be read into the CPU data cache, it also requires the CPU to perform extra work to extract misaligned header fields, such as the 32-bit IP destination address as one example. This extra work includes additional load instructions, where one load instruction might suffice on a properly aligned header, as well as shifting and concatenating the data returned from the load instructions to form the desired single field. Some of the CPU processing is directed to executing extra logic to handle different misalignments for different types of packets.
The throughput of many current routers is limited by the processing capacity of the CPU, i.e., the router performance is said to be CPU limited. To improve throughput of such routers, it is desirable to relieve the CPU load and replace some of the software functionality with hardware functionality, without losing the flexibility to adapt to evolving protocols.
Based on the foregoing, there is a clear need to provide a hardware assist to find and retrieve the layer 2.5 and layer 3 header information in every packet received by the router without losing the flexibility to adapt to evolving protocols. In general, there is a need to provide a hardware assist to find and retrieve header information for a network protocol encapsulated in the payload of a lower layer network protocol.